COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00006 ENDMK
C⊗;
.device xgp
.font 1 "basl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "basi30" <<var>>
.font 4 "basb30" <<bold>>
.evenleftborder←oddleftborder←1100;
.page frame 52 high 79 wide;
.area text lines 1 to 51 chars 1 to 79;
.place text;
.TURN ON "←%";
.NOFILL
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY



←CS 206         COMPUTING WITH SYMBOLIC EXPRESSIONS        FALL 1974
←MIDTERM EXAM

%1←Open Books and Notes




.FILL
	Write  LISP  functions  as  follows  using  the  M-expression
notation used in class:
.SKIP 2
1.	%3get%2[%3y, p%2]%1, where %3y%1 is an S-expression and %3p%1
is a list of A's and D's, is the subexpression of %3y%1 obtained from %3y%1
by taking %4car%1 and %4cdr%1 successively according to the elements of %3p%1.
Thus

	%3get%2[(A ((B) C) (B)), (D A A)] = (B).%1
.SKIP 2
2.	%3point%2[%3x, y%2] is a list of A's and D's such that
%3get%2[%3y, point%2[%3x, y%2]] is the left-most occurrence of the
S-expression %3x%1 in the S-expression %3y%1. Thus

	%3point%2[(B), (A ((B) C) (B))] = (D A A).%1
.SKIP 2
3.	%3allpoint%2[%3x, y%2]%1 is a list of all lists %3p%1 of A's
and D's such that %3get%2[%3y, p%2] = %3x%1.  Thus

	%3allpoint%2[(B), (A ((B) C) (B))] = ((D A A) (D D A)).%1
.SKIP 2
4.	Let a matrix be represented by a list of its rows and each row
by a list of its elements.  %3transpose u%1 is the transpose of the
matrix %3u%1, e.g.

	%3transpose %2((A B C) (D E F) (G H I)) = ((A D G) (B E H) (C F I)).%1
.SKIP 2
5.	Let a set be represented by a list %3u%1 of all its elements.
%3power u%1 is a list of %4all%1 the subsets of %3u%1.  Thus

	%3power %2(A B C) = (NIL (A) (B) (C) (A B) (A C) (B C) (A B C)).%1

I don't especially care about the order of the elements of %3power u%1.